package l.l.w.CodingInterviews;

/**
 * Created by Xingyin Wang on 2018/4/14/0014.
 * 要统计 n的阶乘中 末尾 0的个数。
 * 主要看 其中有多少个5相乘末尾就有多少个0，因为 偶数的个数肯定比5的个数多
 * 比如出现一个5:可定末尾多一个0,25的话末尾多两个0,125的话末尾多3个零
 * N! = 5(K)*5(K-1)*5(K-2)*...*10*5*A
 *    =5^K * K!*A
 * f(n) = K + f(K) 递归式！！！！！！！
 * 其中A指的是 除去5为因子的数中剩下的数eg:
 * 10!= 10*5 *9*8*7*6*4*3*2*1;
 */
public class n阶乘结果尾部0的个数 {
    public int getZeros(int n){
        if(n == 0) return 0;
        int k = n/5;
        return k + getZeros(k);
    }

    public static void main(String[] args) {
        int result = new n阶乘结果尾部0的个数().getZeros(1050);
        String str = "1410188200745141400252996925676992827609427883860681102196565498836336759274700571301062342565763667730574384945641799898255183843797277503390234956935070394479008695945171075361751490266255689101148400638952696890761606725201668092011058223584197411362725808136521522042355331881040677201517524336650583177256411366707450357076114921552137231355444540586815705134573123811035652300829258848866779288445345880939714666466690931600352950947986039996432744118754275201288974846584827623137897792122234828866268708808373651276334848174069438274783771825876627128631153710955178645802336438821598373242525172486367974756812461614902930111917189057714749908028994429977492262359339566774968421933826661845573051906637774350159842777201017432451096856729583848901554363821690871963837317325736243872364148002548730698225622458872512196920911448958125730334065147981692621576246557948729307409911196659268977449824737887320133166571859768610902901473947123457650502571110106359050311523447786812407139365812881583625481044458877349531018685432954716465488394115659122958734526255536933591914359738150594232473711291251674238772555271930793815825985192385373959108468804902794091333308997906654387218990210896432316359969692946647542629459647405723220544167040523889230769503152154177529658591214286091920818334885793018545403374623359640495796839709709384014013012687979103444399633192318216277501509029976296018451103357572826768431048432485483904156377949766394422704783101532471054714207760435511464546800957250453788222377134546592645406967452675959535949763038875966331731971129199721214052529127807792669916640919732183579343359239597918703189536631735584104688709458017493330567389003035699210216919159335873580170482127718603055097898778534952746567262220574405875417584645973964359858336242322940751239914457356958486503721361054938154425602356741007273505642819375318812777259929805604278204113178492040885487253497253599744730743581176164725418840085566636342828519091247494824276253539056065078460524088183488674664479782491935751641451986001983862705359408369452209318497499455387591386320304376709778016052197826525984538725046076767350582105555907369126126599357472133535283786257752742361071712371083162246333227880188819486706970859272715412889313443305257503562357007473653496252819471178088373765780168140628517776493336902711979149445247736765162103192806316969933073702060508523674642586433795221440274867588588796999943822914833791154288328704000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
        System.out.println(result);
        int count = 0;
        for(int i = str.length() - 1; i >= 0; --i){
            if(str.charAt(i) == '0')count++;
            else break;
        }
        System.out.println(count);
    }
}
